class Solution:
    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
        def valid_path(node_routed, m):
            if m == 0:
                return node_routed
            routes = defaultdict(lambda: 0)
            for src in node_routed:
                for node in maps[src]:
                    routes[node] += node_routed[src]
            return valid_path(routes, m-1)

        maps = defaultdict(list)
        for a, b in relation:
            maps[a].append(b)
        return valid_path({0: 1}, k)[n-1]
